This invention relates to a method, a device, a computer readable medium and a computer program element for matching fingerprints.
The word xe2x80x9cfingerprintxe2x80x9d is herein used as a representative of a fingerprint or a like pattern or figure. More particularly, the fingerprint may be an actual finger, a palm print, a toe print, a soleprint, a squamous pattern, and a streaked pattern composed of streaks. The fingerprint may also be a diagram drawn by a skilled person to represent a faint fingerprint which is, for example, left at the scene of a crime.
The xe2x80x9cmatchingxe2x80x9d is for identification of a fingerprint with reference to a plurality of known reference fingerprints. The matching may also be for discrimination, collation, and/or verification of the fingerprint.
In the following, the fingerprint which is to be recognized is called a search fingerprint. A stored fingerprint which is compared with said search fingerprint is called reference fingerprint.
U.S. Pat. No. 5,633,947 describes a method and an apparatus for fingerprint characterization and recognition using an auto correlation approach. A fingerprint image is captured and a binary image of said fingerprint image is determined. Furthermore, said binary image is replicated. Said replica is overlaid on said binary image and an autocorrelation pattern having a displacement modulus equal to a fractional part of the mean fingerprint inter-ridge spacing and a displacement vector rotated through a vector argument in incremental steps is generated.
U.S. Pat. No. 5,493,621 discloses an approach to match a fingerprint by setting up a graph. A master point is the minutia nearest to a center. A sub-branch point is then selected from the nearest point to the master point in each quadrant, followed by sub-sub-branch points in increasing distance. Positional relationship between each branch point with the master point and the sub-sub-branch points in each quadrant are recorded as well as the number of branch points. These data are subsequently used for matching.
In U.S. Pat. No. 4,896,363 a distance spectrum is used for fingerprint matching. In this method, a set of points representative of the characteristic features of a fingerprint image and a set of points representative of the characteristic features of a reference image are determined, respectively. For each point in the set of points, a spectrum of values representing the distances between the point and each other point in the set of points is calculated.
U.S. Pat. No. 4,790,564 describes a method in which at least one search print minutia is replicated by varying at least one of its coordinates of location and angle, thereby obtaining at least one additional minutia which is different from said search print minutia in at least one of said coordinates. Said search print minutia is compared against the minutiae of pre-stored file prints.
In U.S. Pat. No. 4,135,147 means responsive to minutiae of first and second patterns for selectively generating a plurality of sets of neighborhood comparison signals representative of the closeness of match and coordinate and orientation displacements between minutiae neighborhoods of the first and second patterns are described. Each set of neighborhood comparison signals comprises a match score and associated coordinate and orientation displacement signals respectively representative of the closeness of match and coordinate and orientation displacements between a minutiae neighborhood of the first minutiae pattern and a minutiae neighborhood of the second pattern. The comparison uses a plurality of three-dimensional ranges of different displacements in a three-coordinate system for adding in each three-dimensional range all match scores whose associated sets of displacement signals represent displacements lying within that three-dimensional range in order to find the three-dimensional range having the highest combined match score, the highest combined match score being indicative of the relative closeness of match between the first and second patterns.
Block-based matching of fingerprints is described in U.S. Pat. No. 5,239,590.
U.S. Pat. No. 5,613,014 describes a method to match fingerprints using an attribute relational graph.
In U.S. Pat. No. 5,631,972 a hyperladder approach is used to perform fingerprint matching.
U.S. Pat. No. 4,646,352 describes a method and a device for matching fingerprints, wherein a pair candidate list is formed by selecting minutia pairs with reference to a minutia list showing original position and direction data given for minutiae by principal coordinate systems preliminarily selected on a search and a file fingerprint and those relation data of the minutiae which are substantially independent of the coordinate systems. One of the coordinate systems is transformed by those optimum amounts to provide transformed position and direction data which are decided by the original position and direction data of the minutia pairs of the pair candidate list. A pair list is formed by precisely selecting minutiae from the pair candidate list with reference to the transformed position and direction data and the original position and direction data given by the other principal coordinate system and to the relation data. On forming the pair list, an additional minutia list is preferably formed which shows the transformed position and direction data and the last-mentioned original position and direction data together with the relation data.
A minutiae consists of a set of invariant and disciminating features of a fingerprint. It is a local discontinuity of a fingerprint ridge (ridge ending and ridge bifurcation).
One of the disadvantages of these known methods are the uncertainty of the matching result.
It is thus an object of the present invention to determine a degree of match between a search fingerprint and a reference fingerprint with a higher degree of certainty than it is possible using the known methods described above.
The object is met with a method, a device, a computer readable medium and a computer program element for matching fingerprints with features according to the independent claims.
A method for determining a degree of match between a search fingerprint and a reference fingerprint comprising the following steps:
a) Extracting at least one first search feature from a first region of said search fingerprint thereby forming a local search feature vector,
b) Extracting at least one second search feature from a second region of said search fingerprint thereby forming a global search feature vector, wherein said second region comprises said first region,
c) Determining a first similarity degree by comparing said local search feature vector with a local reference feature vector of said reference fingerprint,
d) Determining a second similarity degree by comparing said global search feature vector with a global reference feature vector of said reference fingerprint and using said first similarity degree,
e) Determining said degree of match from said second similarity degree.
A device for determining a degree of match between a search fingerprint and a reference fingerprint comprising:
a) Means for extracting at least one first search feature from a first region of said search fingerprint thereby forming a local search feature vector,
b) Means for extracting at least one second search feature from a second region of said search fingerprint thereby forming a global search feature vector, wherein said second region comprises said first region,
c) Means for determining a first similarity degree by comparing said local search feature vector with a local reference feature vector of said reference fingerprint,
d) Means for determining a second similarity degree by comparing said global search feature vector with a global reference feature vector of said reference fingerprint and using said first similarity degree,
e) Means for determining said degree of match from said second similarity degree.
A computer readable medium having a program recorded thereon, where the program is to make the computer execute a procedure, comprising the following steps for determining a degree of match between a search fingerprint and a reference fingerprint:
a) Extracting at least one first search feature from a first region of said search fingerprint thereby forming a local search feature vector,
b) Extracting at least one second search feature from a second region of said search fingerprint thereby forming a global search feature vector, wherein said second region comprises said first region,
c) Determining a first similarity degree by comparing said local search feature vector with a local reference feature vector of said reference fingerprint,
d) Determining a second similarity degree by comparing said global search feature vector with a global reference feature vector of said reference fingerprint and using said first similarity degree,
e) Determining said degree of match from said second similarity degree.
A computer program element which is to make the computer execute a procedure comprising the following steps for determining a degree of match between a search fingerprint and a reference fingerprint:
a) Extracting at least one first search feature from a first region of said search fingerprint thereby forming a local search feature vector,
b) Extracting at least one second search feature from a second region of said search fingerprint thereby forming a global search feature vector, wherein said second region comprises said first region,
c) Determining a first similarity degree by comparing said local search feature vector with a local reference feature vector of said reference fingerprint,
d) Determining a second similarity degree by comparing said global search feature vector with a global reference feature vector of said reference fingerprint and using said first similarity degree,
e) Determining said degree of match from said second similarity degree.
By the invention local and global information (features) are used, thereby enhancing the certainty of the result.
The result is robust to a nonlinear deformation of an image of the fingerprint due to variation in pressure and the pressing manner.
A further advantage of the invention is, that the method is fast to compute thereby being suitable for an online fingerprint verification and/or fingerprint identification.
The invention may be implemented in a programmable computer device as well as with a special electronic circuit.
Advantageous embodiments of the invention are claimed in the dependent claims.
The further described embodiments are valid for the method as well as the device, the computer readable medium and the computer program.
Said features may describe minutiae of said fingerprints or a relation between minutiae of said fingerprints.
Features may be used which are independent from rotation and/or translation of the fingerprints compared with a given coordinate system.
The invention may further comprise the following features:
said first region comprises a given first amount of neighbor minutiae,
said second region comprises a given second amount of neighbor minutiae,
said second amount is larger than said first amount.
The invention may further comprise the following features:
Determining said first similarity degree for all minutiae in said first region,
Determining a best match local structure pair of minutiae by using said first similarity degrees,
Aligning all minutiae in said second region based on said best match local structure pair, thereby forming said global search feature vector.
In a further embodiment, said first similarity degree cl(k1, k2) is determined using the following formula:       c1    ⁡          (              k1        ,        k2            )        =      {                                                                      b1                -                                  W                  xc3x97                                      "LeftBracketingBar"                                                                  FL                        k1                        S                                            -                                              FL                        k2                        R                                                              "RightBracketingBar"                                                              b1                        ,                                                              if              ⁢                              xe2x80x83                            ⁢              W              xc3x97                              "LeftBracketingBar"                                                      FL                    k1                    S                                    -                                      FL                    k2                    R                                                  "RightBracketingBar"                                       less than             b1                                                            0            ,                                    Others                    
wherein
bl is a freely selectable local threshold,
W is a freely selectable weight vector that specifies the weight associated with each component of said feature vector,
FLk1S is a local search feature vector of minutia k1,
FLk2R is a local reference feature vector of minutia k2.
Furthermore, said second similarity degree cg(k1, k2) may be determined using the following formula:       cg    ⁡          (              k1        ,        k2            )        =      {                                                                      c1                ⁡                                  (                                      k1                    ,                    k2                                    )                                            ,                                                                          if                ⁢                                  xe2x80x83                                ⁢                                  "LeftBracketingBar"                                                            FG                      k1b                      S                                        -                                          FG                      k2b                      R                                                        "RightBracketingBar"                                             less than               bg                                                                          0              ,                                            Others                              ,      
wherein
bg is a freely selectable global threshold vector,
FGk1bS is a global search feature vector of minutia k1,
FGk2bR is a global reference feature vector of minutia k2.
In a further preferred embodiment of the invention said degree of match is determined using the following formula:             m      ⁢              xe2x80x83            ⁢      s        =                  ∑                  cg          ⁡                      (                          k1              ,              k2                        )                                      max        ⁡                  (                      N1            ,            N2                    )                      ,
wherein N1 and N2 are the numbers of minutiae in a common region of said search fingerprint and said reference fingerprint.
By these features, even a better and more robust result is achieved.